package priv.pront.code.national.acwing.dp.bags;

import java.util.*;

public class Acwing532_货币系统 {

    static int t;
    static int[] a;
    static long[] dp;
    static List<Integer> list = new ArrayList<>();
    static List<Integer> ans = new ArrayList<>();
    static boolean[] st;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        t = scanner.nextInt();
        while (t-- > 0) {
            st = new boolean[25010];
            Arrays.fill(st, true);
            int n = scanner.nextInt();
            a = new int[n + 1];
            dp = new long[25010];
            for (int i = 1; i <= n; i++) a[i] = scanner.nextInt();
            dp[0] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = a[i]; j <= 25009; j++) {
                    dp[j] += dp[j - a[i]];
                    if (dp[j] > 0 && !list.contains(j)) list.add(j);
                }
            }
            list.add(0);
            Collections.sort(list);
            for (int i = 1; i < list.size(); i++) {
                if (st[list.get(i)]) {
                    for (int j = 2 * list.get(i); j <= 25009; j += list.get(i)) {
                        st[j] = false;
                    }
                    // FIXME
                    for (int j = ans.size() == 0 ? 0 : ans.get(ans.size() - 1); j < list.get(i); j++) {
                        st[j] = false;
                    }
                    ans.add(list.get(i));
                }
            }
            System.out.println(ans.size());
        }
    }

    /*正解*/
//    private static void solve(int[] arr, int n, boolean[] dp, StringBuilder sb) {
//        Arrays.sort(arr, 0, n);
//        for (int i = 1; i <= arr[n - 1]; ++i) {
//            dp[i] = false;
//        }
//        int cnt = n;
//        for (int i = 0; i < n; ++i) {
//            if (dp[arr[i]]) {
//                cnt--;
//                continue;
//            }
//            for (int j = arr[i]; j <= arr[n - 1]; ++j) {
//                dp[j] |= dp[j - arr[i]];
//            }
//        }
//        sb.append(cnt).append("\n");
//    }
//
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int T = in.nextInt();
//        boolean[] dp = new boolean[25001];
//        dp[0] = true;
//        int[] arr = new int[101];
//        StringBuilder sb = new StringBuilder();
//        for (int j = 0; j < T; ++j) {
//            int n = in.nextInt();
//            for (int i = 0; i < n; ++i) {
//                arr[i] = in.nextInt();
//            }
//            solve(arr, n, dp, sb);
//        }
//        in.close();
//        System.out.print(sb);
//    }
}
